package kmp;



import static BinaryTree.SerializeAndReconstructTree.*;

public class LinkedListInBinaryTree {

    public static void main(String[] args) {
        String tree1 = "a,a,a,#,#,b,#,#,a,a,a,b,#,#,#,c,#,#,#";
        String tree2 = "a,a,a,#,#,b,#,#,b,a,a,b,#,#,#,c,#,#,#";
        Node node = reconByPreString(tree1, '#', ",");
        Node node1 = reconByPreString(tree2, '#', ",");

        System.out.println(isSubPath(node, new int[]{'a', 'a', 'a', 'b'}, 4));
        System.out.println(isSubPath(node1, new int[]{'a', 'a', 'a', 'b'}, 4));
    }

    public static class ListNode {
        int val;
        ListNode next;
    }


    public static boolean isSubPath(ListNode head, Node root) {
        int m = 0;
        ListNode tmp = head;
        while (tmp == null) {
            m++;
            tmp = tmp.next;
        }
        int[] s2 = new int[m];
        m = 0;
        while (head != null) {
            s2[m++] = head.val;
            head = head.next;
        }
        return isSubPath(root, s2, m);
    }

    private static boolean isSubPath(Node root, int[] s2, int m) {
        int[] next = nextArray(s2, m);
        return find(s2, next, root, 0);
    }

    private static int[] nextArray(int[] array, int m) {
        int[] next = new int[m];
        next[0] = -1;
        next[1] = 0;
        int i = 2, cn = 0;

        while (i < m) {
            if (array[i - 1] == array[cn]) {
                next[i++] = ++cn;
            } else if (cn > 0) {
                cn = next[cn];
            } else {
                next[i++] = 0;
            }
        }
        return next;
    }

    /**
     * @param s2   要匹配的数组
     * @param next 匹配数组的next数组
     * @param cur  当前节点
     * @param i    匹配到的位置
     * @return true:能把链表匹配出来
     */
    private static boolean find(int[] s2, int[] next, Node cur, int i) {
        // 到我的父节点已经可以把链表匹配出来了
        if (i == s2.length) {
            return true;
        }

        // 到我的父节点没有把链表匹配出来了，但是我为空，所以不能匹配出数组
        if (cur == null) {
            return false;
        }

        // 跳出条件: i跳到了-1的位置 or 节点值和链表值匹配了
        while (i >= 0 && cur.value != s2[i]) {
            i = next[i];
        }
        // 左节点，右节点两个分支继续去匹配
        return find(s2, next, cur.left, i + 1) || find(s2, next, cur.right, i + 1);
    }
}
